import sun.reflect.generics.tree.Tree;

import java.util.*;

public class Solution {

    class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * 求一棵树的最大宽度
     * 思路：1.利用两个队列来解决
     *      2，创建两个队列，queue 一个放树里面的元素 ，indexQ一个放与之对应的下标
     *      3.创建两个循环，外层循环遍历整棵树，内层循环遍历每一层树，每一层树遍历的条件是队列的大小
     *      4.首先将初始结点root，和下标 1 放入队列中
     *      5.再去创建最大宽度的变量
     *      6.在放元素下标的队列中定义两个变量，indexFirst 值为 indexQ.peek()的值，index的值为 indexFirst
     *      7.定义一个辅助结点cur，cur为queue每次弹出的值，(在内层循环中弹)判断cur的左结点 和右结点为不为空
     *      8.不为空，将结点放入queue队列中，并将与之对应的下标放入indexQ中
     *      9.内层循环结束后计算每一层的宽度 width
     *      10.再将width的值与maxWidth进行比较，将两者的最大值放入到maxWidth中
     *      11.最后返回maxWidth的值
     * @param root
     * @return
     */
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return  0;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        Queue<Integer> indexQ = new ArrayDeque<>();
        queue.add(root);
        indexQ.add(1);
        int maxWidth = 0;
        while (queue.size() > 0 && indexQ.size() > 0) {
            int size = queue.size();
            int width = 0;
            int indexFirst = indexQ.peek();
            int index = indexFirst;
            while (size != 0 ) {
                TreeNode cur = queue.poll();
                index = indexQ.poll();
                if (cur != null) {
                    if (cur.left != null) {
                        queue.add(cur.left);
                        indexQ.add(index * 2);
                    }
                    if (cur.right != null) {
                        queue.add(cur.right);;
                        indexQ.add(index * 2 +1);
                    }
                }else {
                    return 0;
                }
                size--;
            }
            width = index - indexFirst + 1;
            maxWidth = Math.max(maxWidth,width);
        }
        return maxWidth;
    }

    /**
     * 判断一棵树是否为完全二叉树
     * 思路：1.利用一个队列来解决
     *      2.首先判断root为不为空，不为空直接放入到队列中
     *      3.定义一个辅助结点cur，用来接受每次queue中每次弹出的值
     *      4.创建一个while循环，只要cur不为null就将cur的左结点和右结点放入到队列中
     *      5.第一个while循环结束后，cur为空了，再去创建第二个while循环
     *      6.第二个while循环判断queue中元素是否都为空，不是返回false
     *      7.两个循环都走完了，说明此时这颗树为完全二叉树
     * @param root
     * @return
     */
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode cur = queue.poll();
        while (cur != null) {
            queue.offer(cur.left);
            queue.offer(cur.right);
            cur = queue.poll();
        }
        while (!queue.isEmpty()) {
            if (queue.poll() != null) {
                return false;
            }
        }
        return true;
    }

    /**
     * 递增顺序查找树
     * 思路：1.创建一个链表用来接收值
     *      2.实现一个中序遍历的方法，用来把二叉搜索树的值放入到链表
     *      3.再根据链表中的值创建一颗递增顺序查找树
     * @param root
     * @return
     */
    public TreeNode increasingBST(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        increasingBSTChild(root,list);
        TreeNode treeNode = new TreeNode(0);
        TreeNode cur = treeNode;
        for (Integer val : list) {
            cur.right = new TreeNode(val);
            cur = cur.right;
        }
        return treeNode.right;

    }

    public void increasingBSTChild(TreeNode root,List<Integer> list) {
        if (root == null) {
            return;
        }
        increasingBSTChild(root.left,list);
        list.add(root.val);
        increasingBSTChild(root.right,list);
    }

    /**
     * 合并两颗二叉树
     * 思路：1.root1 为空时返回 root2
     *      2.root2 为空时返回 root1
     *      3.都不为空时，设置root的val = root1的val + root2的val
     *      4.再去递归 root的左树，传 root1的left 和 root2的left 为参数
     *      5.再去递归 root的右树，传 root1的right 和 root2的right 为参数
     *      6.最后返回根结点 root
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        TreeNode root = new TreeNode(root1.val + root2.val);
        root.left = mergeTrees(root1.left,root2.left);
        root.right = mergeTrees(root1.right,root2.right);
        return root;
    }

    /**
     * 把二叉搜索树转换为累加树
     * 思路：1.实现一个方法 convertBSTChild 采用右，根，左的方式去修改原来二叉搜索树的val值
     *      2.递归结束的条件，判断root为不为空，为空直接返回
     *      3.递归root的左树，拿到最右边结点的值
     *      4.记录每次递归结点的值，一次相加，赋值给递归的结点
     *      5.再去递归root的左结点
     *      6.实现完 convertBSTChild 方法，返回根结点 root
     * @param root
     * @return
     */
    public TreeNode convertBST(TreeNode root) {
        convertBSTChild(root);
        return root;
    }
    public int sum = 0;
    public void convertBSTChild(TreeNode root) {
        if (root == null) {
            return;
        }
        convertBSTChild(root.right);
        sum = sum + root.val;
        root.val = sum;
        convertBSTChild(root.left);
    }

    class MyCompartor implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    }

    /**
     * 最后一块石头
     * @param stones
     * @return
     */
    public int lastStoneWeight(int[] stones) {
        Queue<Integer> q = new PriorityQueue<>(new MyCompartor());
        for (int stone : stones) {
            q.offer(stone);
        }
        while (q.size() > 1) {
            int x = q.poll();
            int y = q.poll();
            int dif = Math.abs(x-y);
            if (dif > 0) {
                q.offer(dif);
            }
        }
        if (q.peek() == null) {
            return 0;
        }
        return q.peek();
    }


}
